/*
 * @lc app=leetcode.cn id=310 lang=golang
 *
 * [310] 最小高度树
 */

// @lc code=start

func findMinHeightTrees(n int, edges [][]int) []int {
	if n < 1 {
		return []int{}
	}

	nodeToNode := make(map[int][]int)
	// nodeEdgeNums := make([]int, n)
	for i := 0; i < n-1; i++ {
		if _, ok := nodeToNode[edges[i][0]]; ok {
			nodeToNode[edges[i][0]] = append(nodeToNode[edges[i][0]], edges[i][1])

		} else {
			nodeToNode[edges[i][0]] = []int{edges[i][1]}

		}
		if _, ok := nodeToNode[edges[i][1]]; ok {
			nodeToNode[edges[i][1]] = append(nodeToNode[edges[i][1]], edges[i][0])
		} else {
			nodeToNode[edges[i][1]] = []int{edges[i][0]}
		}
		// nodeEdgeNums[edges[i][0]]++
		// nodeEdgeNums[edges[i][1]]++
	}
	route := make([]int, n)
	isVisit := make([]int, n)
	route[0] = -1
	bfs := []int{0}
	isVisit[0] = 1
	last := 0
	var bfsfunc func()
	bfsfunc = func() {
		for len(bfs) != 0 {
			temp := make([]int, 0, n)
			for _, v := range bfs {
				// if isVisit[v] == 1 {
				// 	continue
				// }
				for _, v2 := range nodeToNode[v] {
					if isVisit[v2] == 1 {
						continue
					}
					isVisit[v2] = 1
					route[v2] = v
					temp = append(temp, v2)
				}
			}
			last = bfs[0]
			bfs = temp
		}
	}
	bfsfunc()
	for i := range isVisit {
		isVisit[i] = 0
		route[i] = 0

	}

	bfs = []int{last}
	route[last] = -1
	isVisit[last] = 1
	bfsfunc()

	route_node := make([]int, 0, n)
	for last != -1 {
		route_node = append(route_node, last)
		last = route[last]
	}
	index := len(route_node) / 2
	if len(route_node)%2 == 0 {
		return route_node[index-1 : index+1]
	} else {
		return route_node[index : index+1]
	}

}

// @lc code=end
